package com.jinan.algorithm.dynamicProgramming;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，
 * 其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 */
class DailyTemperatures {
    public static void main(String[] args) {
        int[] temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
        DailyTemperatures dailyTemperatures = new DailyTemperatures();
        int[] answer = dailyTemperatures.dailyTemperatures(temperatures);
        System.out.println(Arrays.toString(answer));
        Stack<Integer> stack = new Stack<>();

    }

    //    暴力算法
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        answer[n - 1] = 0;
        if (n <= 1) {
            return answer;
        }
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    answer[i] = j - i;
                    break;
                } else {
                    answer[i] = 0;
                }
            }
        }
        return answer;
    }


    /**
     * 从后往前面遍历， 利用ans数组直接跳转到下一个更大的数进行比较，直到找到比当前i所在位置温度更高的位置
     *
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures2(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        if (n <= 1) {
            return answer;
        }
        for (int i = n - 2; i >= 0; i--) {
            int j = i + 1;
            while (j < n && temperatures[j] <= temperatures[i] && answer[j] != 0) {
                j += answer[j];
            }
            if (j < n && temperatures[j] > temperatures[i]) {
                answer[i] = j - i;
            }
        }
        return answer;
    }

    /**
     * 维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。
     * 如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。
     * 正向遍历温度列表。对于温度列表中的每个元素 temperatures[i]，
     * 如果栈为空，则直接将 i 进栈，如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 temperatures[prevIndex] 和当前温度 temperatures[i]，
     * 如果 temperatures[i] > temperatures[prevIndex]，则将 prevIndex 移除，
     * 并将 prevIndex 对应的等待天数赋为 i - prevIndex，
     * 重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈。
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures1(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        answer[n - 1] = 0;
        if (n <= 1) {
            return answer;
        }
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int j = stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }
        return answer;
    }

    public static boolean isValid(String s){
        Deque stack = new LinkedList();
        for (char c : s.toCharArray()){
            if (c=='('||c=='['||c=='{'){
                stack.push(c);
            }else {
                if (stack.isEmpty()){
                    return false;
                }
                if (c==')'){
                    if ((char)stack.pop()!='('){
                        return false;
                    }
                }
                else if (c==']'){
                    if ((char)stack.pop()!='['){
                        return false;
                    }
                }
                else if (c=='}'){
                    if ((char)stack.pop()!='{'){
                        return false;
                    }
                }
            }
        }
        if (!stack.isEmpty()){
            return false;
        }
        return true;
    }
}